#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn=10000;
struct node{
    char c;//??
    int cnt;//????
    int l,r;
    int index;
    bool operator<(const node &a)const{
        return cnt>a.cnt;
    }
}a[maxn];
priority_queue<node> p;

void dfs(int root,string ans){
    if(a[root].l==-1){
        cout<<a[root].c<<":"<<ans<<endl;
        return ;
    }
    dfs(a[root].l,ans+"0");
    dfs(a[root].r,ans+"1");
    return ;
}

int main()
{
    IOS;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].c>>a[i].cnt;
        a[i].l=-1;a[i].r=-1;
        a[i].index=i;
        p.push(a[i]);
    }
    int root=n-1,lchild,rchild;
    //??????
    while(p.size()>1){
        root++;
        lchild=p.top().index;
        p.pop();
        rchild=p.top().index;
        p.pop();
        a[root].l=lchild;
        a[root].r=rchild;
        a[root].index=root;
        a[root].cnt=a[lchild].cnt+a[rchild].cnt;
        p.push(a[root]);
    }
    p.pop();
    //???????
    dfs(root,"");
    getchar();
    getchar();
    return 0;
}
